package com.ly.algorithm.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname Problem78
 * @Description
 *
 * *
 *  * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *  *
 *  * 说明：解集不能包含重复的子集。
 *  *
 *  * 示例:
 *  *
 *  * 输入: nums = [1,2,3]
 *  * 输出:
 *  * [
 *  *    [3],
 *  *   [1],
 *  *   [2],
 *  *   [1,2,3],
 *  *   [1,3],
 *  *   [2,3],
 *  *   [1,2],
 *  *   []
 *  * ]
 *  *
 *  *
 *
 *
 * @Date 2020/12/14 19:19
 * @Author 冷心影翼
 */
public class Problem78 {

	public static void main(String[] args) {
		Solution78 solution78 = new Solution78();
		List<List<Integer>> subsets = solution78.subsets(new int[]{1, 2, 3});
		System.out.println(subsets);
	}
}


class Solution78 {

	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> cur = new ArrayList<>();
		backTracking(0,nums,cur,res);
 		return res;
	}

	public void backTracking(int startIndex,int[] nums,List<Integer> cur,List<List<Integer>> res) {
		res.add(new ArrayList<>(cur));
		// i= 0 res = [ [1] ] cur = [1] i= 1 res = [ [1] [1,2] ] cur = [1,2]
		// i= 2 res = [ [1] [1,2] [1,2,3] ] cur = [1,2,3]
		// i= 1  remove cur=[1,2]
		for(int i= startIndex;i<nums.length;i++) {
			cur.add(nums[i]);
			backTracking(i+1,nums,cur,res);
			cur.remove(cur.size()-1);
		}
	}
}